package 我的Java学习_算法基础.day_05;

public class _080_符串匹配之RabinKarp_上 {
    public static void main(String[] args) {
        String s ="ABABAB";
        String key = "AB";
        match(key,s);
    }
    //朴素算法
    static int seed = 31;
    static long hash(String s){
        long hash = 0;
        for(int i = 0;i<s.length();i++){
            hash=hash*seed+s.charAt(i);
        }
        return hash%Long.MAX_VALUE;
    }

    /**
     *
     * @param key 模式
     * @param s 原串
     */
    private static void match(String key,String s){
        long hash_key=hash(key);
        int key_len = key.length();
        for(int i =0;i+key_len<=s.length();i++){
            long hash_i = hash(s.substring(i,i+key_len));
            if(hash_i==hash_key){
                System.out.println("match:"+i);
            }
        }
    }
}
